package com.mccken.practice.algorithm.tree_02;

import java.util.LinkedList;
import java.util.Queue;

import com.mccken.practice.algorithm.common.TreeNode_Common;

/**
 * 前序遍历： 左中右
 * 中序遍历： 中左右
 * 后序遍历： 左右中
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-27 17:20
 **/
public class TreeCodec implements ICodec {

	// 代表字符串分隔符 
	private String SEP = ",";

	// 代表 null 空指针的字符
	private String NULL = "#";

	enum TraverseModeEnum {
		PRE, MID, POST,
	}

	private TraverseModeEnum selectMode() {
		return TraverseModeEnum.POST;
	}

	// traverse 遍历
	// 将二叉树打平为字符串
	private void traverse_01(TreeNode_Common treeNodeCommon, StringBuilder sb_) {

		if (treeNodeCommon == null) {
			sb_.append(NULL).append(SEP);
			return;
		}

		// 前序遍历位置
		sb_.append(treeNodeCommon.val).append(SEP);

		traverse_01(treeNodeCommon.left, sb_);
		traverse_01(treeNodeCommon.right, sb_);
	}

	// 层级遍历二叉树 框架
	private void traverse_02(TreeNode_Common root) {
		if (root == null) {
			return;
		}

		Queue<TreeNode_Common> q = new LinkedList<>();
		q.offer(root);

		while (!q.isEmpty()) {
			TreeNode_Common cur = q.poll();
			// 层级遍历代码位置
			System.out.println(cur.val);

			if (cur.left != null) {
				q.offer(cur.left);
			}

			if (cur.right != null) {
				q.offer(cur.right);
			}
		}
	}

	@Override
	public String serialize(TreeNode_Common root) {
		StringBuilder sb = new StringBuilder();
		serialize_pre(root, sb);
		return sb.toString();
	}

	// 将字符串反序列化为二叉树
	@Override
	public TreeNode_Common deserialize(String data) {
		// 将字符串转化成列表
		TraverseModeEnum mode = this.selectMode();
		switch (mode) {
			case MID:
			case POST:
				return deserialize_post(data);

			case PRE:
			default:
				return deserialize_pre(data);
		}

	}

	private TreeNode_Common deserialize_pre(String data) {
		LinkedList<String> nodes = new LinkedList<>();
		for (String str : data.split(SEP)) {
			nodes.addLast(str);
		}
		return deserialize_pre(nodes);
	}

	// 前序遍历
	private void serialize_pre(TreeNode_Common root, StringBuilder sb) {
		if (root == null) {
			sb.append(NULL).append(SEP);
			return;
		}

		sb.append(root.val).append(SEP);

		serialize_pre(root.left, sb);
		serialize_pre(root.right, sb);
	}

	private TreeNode_Common deserialize_pre(LinkedList<String> nodes) {
		if (nodes.isEmpty()) {
			return null;
		}

		String first = nodes.removeFirst();
		if (first.equals(NULL)) {
			return null;
		}

		TreeNode_Common root = new TreeNode_Common(Integer.parseInt(first));

		root.left = deserialize_pre(nodes);
		root.right = deserialize_pre(nodes);
		return root;
	}

	private void serialize_post(TreeNode_Common root, StringBuilder sb) {
		if (root == null) {
			sb.append(NULL).append(SEP);
			return;
		}

		serialize_post(root.left, sb);
		serialize_post(root.right, sb);

		sb.append(root.val).append(SEP);
	}

	// mccken_mark 这是错误的 后序遍历 思路，是对前序遍历毫无思考的模仿。问题在于，没有正确找到 root 节点
	private TreeNode_Common deserialize_post_error(LinkedList<String> nodes) {
		if (nodes.isEmpty()) {
			return null;
		}

		TreeNode_Common left = deserialize_post_error(nodes);
		TreeNode_Common right = deserialize_post_error(nodes);

		String first = nodes.removeFirst();
		if (first.equals(NULL)) {
			return null;
		}

		TreeNode_Common root = new TreeNode_Common(Integer.parseInt(first));
		root.left = left;
		root.right = right;

		return root;
	}

	/**
	 * 后序遍历形容的一棵树 data: null,null,null,4,2,null,null,3,1
	 * LinkedList<String> nodes 通过 addLast 转化后：  ###42##31
	 * 再转化成树的时候，需要从后面取， removeLast
	 *
	 * @param data
	 * @return
	 */
	private TreeNode_Common deserialize_post(String data) {
		LinkedList<String> nodes = new LinkedList<>();
		for (String str : data.split(SEP)) {
			nodes.addLast(str);
		}
		return deserialize_post(nodes);

	}

	// 后序遍历，拿到的 LinkedList 是倒序的
	private TreeNode_Common deserialize_post(LinkedList<String> nodes) {
		if (nodes.isEmpty()) {
			return null;
		}

		String first = nodes.removeFirst();
		if (first.equals(NULL)) {
			return null;
		}
		TreeNode_Common root = new TreeNode_Common(Integer.parseInt(first));

		root.right = deserialize_post(nodes);
		root.left = deserialize_post(nodes);
		return root;
	}

	// 层级遍历
	public String serialize_hierarchical_traversal(TreeNode_Common root) {
		if (root == null) {
			return "";
		}

		StringBuilder sb = new StringBuilder();
		Queue<TreeNode_Common> q = new LinkedList<>();
		// 塞入root节点
		q.offer(root);

		while (!q.isEmpty()) {
			TreeNode_Common node = q.poll();
			if (node == null) {
				sb.append(NULL).append(SEP);
				continue;
			}
			sb.append(node.val).append(SEP);

			q.offer(node.right);
			q.offer(node.left);
		}

		return sb.toString();
	}

	public TreeNode_Common deserialize_hierarchical_traversal3(String data) {
		if (data == null || data.isEmpty()) {
			return null;
		}

		LinkedList<String> nodes = new LinkedList<>();
		String[] dates = data.split(SEP);
		if (dates[0].equals(NULL)) {
			return null;
		}

		TreeNode_Common root = new TreeNode_Common(Integer.parseInt(dates[0]));
		Queue<TreeNode_Common> q = new LinkedList<>();
		q.offer(root);

		int i = 1;
		while (!q.isEmpty()) {
			TreeNode_Common node = q.poll();

			int leftIndex = 2 * i - 1;
			int rightIndex = 2 * i;

			if (leftIndex < dates.length && dates[leftIndex].equals(NULL)) {
				node.left = new TreeNode_Common(Integer.parseInt(dates[leftIndex]));
				q.offer(node.left);
			} else {
				node.left = null;
			}
			
			if (rightIndex < dates.length && dates[rightIndex].equals(NULL)) {
				node.right = new TreeNode_Common(Integer.parseInt(dates[rightIndex]));
				q.offer(node.right);
			} else {
				node.right = null;
			}
			i++;
		}
		return root;
	}

}
